//Given an array of integers nums sorted in non-decreasing order, find the 
//starting and ending position of a given target value. 
//
// If target is not found in the array, return [-1, -1]. 
//
// You must write an algorithm with O(log n) runtime complexity. 
//
// 
// Example 1: 
// Input: nums = [5,7,7,8,8,10], target = 8
//Output: [3,4]
// Example 2: 
// Input: nums = [5,7,7,8,8,10], target = 6
//Output: [-1,-1]
// Example 3: 
// Input: nums = [], target = 0
//Output: [-1,-1]
// 
// 
// Constraints: 
//
// 
// 0 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// nums is a non-decreasing array. 
// -10⁹ <= target <= 10⁹ 
// 
// Related Topics Array Binary Search 👍 8206 👎 253


package leetcode.editor.en;

public class _34_FindFirstAndLastPositionOfElementInSortedArray {
    public static void main(String[] args) {
        Solution solution = new _34_FindFirstAndLastPositionOfElementInSortedArray().new Solution();
        int[] ints = solution.searchRange1(new int[]{1}, 1);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] searchRange2(int[] nums, int target) {
            if (nums.length==0) {
                return new int[]{-1, -1};
            }
            int first = findFirst2(nums, target);
            int second = findFirst2(nums, target+1);
            if (first == nums.length || nums[first]!=target) {
                return new int[]{-1, -1};
            }
            return new int[]{first, second-1};
        }

        private int findFirst2(int[] nums, int target) {
            int l = 0, r = nums.length;
            while (l<r){
                int mid = l + (r - l) / 2;
                if (nums[mid]<target){
                    l = mid+1;
                }else {
                    r =  mid;
                }
            }
            return l;
        }


        public int[] searchRange1(int[] nums, int target) {
            if (nums.length == 0) {
                return new int[]{-1,-1};
            }
            int first = findFirst1(nums, target);
            int last = findFirst1(nums, target + 1);

            if (first== nums.length || nums[first]!=target) {
                return new int[]{-1, -1};
            }
            return  new int[]{first, last-1};
        }

        private int findFirst1(int[] nums, int target) {
            int l =0, r= nums.length;
            while (l<r){
                int mid = l + (r - l)/2;
                if (nums[mid]<target) {
                    l = mid+1;
                }else {
                    r = mid;
                }
            }
            return l;
        }


        public int[] searchRange(int[] nums, int target) {
            if (nums.length ==0) {
                return new int[]{-1,-1};
            }
            int f = findFirst(nums, target);
            if (f == -1) {
                return new int[]{-1, -1};
            }
            int l = findLast(nums, target);
            return new int[]{f, l};
        }

        private int findLast(int[] nums, int target) {
            int l =0, r = nums.length-1;
            while (l<r){
                int mid = l + (r - l+1) / 2;
                if (nums[mid]>target) {
                    r = mid-1;
                } else {
                    l = mid;
                }
            }
            if (nums[l]==target) {
                return l;
            }
            return -1;
        }

        private int findFirst(int[] nums, int target) {
            int l =0, r = nums.length-1;
            while (l < r){
                int mid = l + (r - l) / 2;
                if (nums[mid]<target) {
                    l = mid+1;
                }else {
                    r = mid;
                }
            }
            if (nums[l]==target) {
                return l;
            }
            return -1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}